#include "gf.h"

// Конструктор поля Галуа
// предусловие: неприводимый полином должен быть положительным
GF::GF(qlonglong polynom, QObject *parent) :
  QObject(parent),
  m_p(2),            // пока что поле может быть лишь характеристики 2
  m_polynom(polynom)
{
#ifdef ERRS
  if ( m_polynom <= 0 ) { // проверка предусловия
    error("GF::GF(): неприводимый полином не положителен.");
  }
#endif

  for (m_m = 1; m_polynom >> m_m != 1; ++m_m); // определить степень примитивного полинома
  m_q = pow(2, m_m);                           // инициализировать мощность поля

  // сформировать таблицу логарифмов и анти-логарифмов (хэш таблицу)
  qlonglong r = 1; // линейный регистр с обратной связью
  qlonglong i = 0; // степень примитивного элемента
  do {
    m_hashTable.insert(i++, r); // добавить в поле
    // сформировать следующий элемент поля
    if ( (r <<= 1) / m_q ) // если обратная связь не нулевая
      r = (m_polynom ^ r) % m_q;
  } while ( r != 1 );
}

// представление элемента поля в виде двоичного вектора
// предусловие: входной элементы должен быть меньше мощности поля
QString GF::toBin(qlonglong x) const {
#ifdef ERRS
  if ( x >= m_q|| x < 0 ) { // проверка предусловия
    error("GF::toBin(): входной элемент не принадлежит данному полю.");
  }
#endif
  QString str = QString::number(x, 2);

  while ( str.size() < m_m ) {
    str.insert(0, '0');
  }

  return str;
}


// вернуть поле
QHash<qlonglong, qlonglong> GF::hashTable() {
  return m_hashTable;
}

// умножение элементов конечного поля
// предусловие: входные элементы должны быть меньше мощности поля
// постусловие: выходной элемент должен быть меньше мощности поля
qlonglong GF::mul(qlonglong x, qlonglong y) const {
#ifdef ERRS
  if ( x >= m_q || y >= m_q || x < 0 || y < 0 ) { // проверка предусловия
    error("GF::mul(): входной элемент не принадлежит данному полю.");
  }
#endif

  if (x == 0 || y == 0) return 0;
  if (x == 1) return y;
  if (y == 1) return x;

  qlonglong i = log(x), // представить элемент x в виде степени примитивного
            j = log(y); // представить элемент y в виде степени примитивного

#ifdef ERRS
  if (i == -1 || j == -1) { // если в таблице нет таких элементов
    error("GF::mul(): в хэш-таблице нет такого элемента.");
  }
#endif

  return alog( (i+j) % (m_q-1) );
}

// деление элементов конечного поля
// предусловие: входные элементы должны быть меньше мощности поля
// постусловие: выходной элемент должен быть меньше мощности поля
qlonglong GF::div(qlonglong x, qlonglong y) const {
#ifdef ERRS
  if ( x >= m_q || y >= m_q || x < 0 || y < 0 ) { // проверка предусловия
    error("GF::div(): входной элемент не принадлежит данному полю.");
  }
#endif

  if (y == 0) error("GF::div(): деление на ноль.");
  if (x == 0) return 0;
  if (y == 1) return x;

  qlonglong i = log(x), // представить элемент x в виде степени примитивного
            j = log(y); // представить элемент y в виде степени примитивного

  return alog( (m_q-1+i-j) % (m_q-1) );
}

// сложение элементов конечного поля
// предусловие: входные элементы должны быть меньше мощности поля
// постусловие: выходной элемент должен быть меньше мощности поля
qlonglong GF::plus(qlonglong x, qlonglong y) const {
#ifdef ERRS
  if ( x >= m_q || y >= m_q || x < 0 || y < 0 ) { // проверка предусловия
    error("GF::plus(): входной элемент не принадлежит данному полю.");
  }
#endif

  return x ^ y;
}

// вернуть обратный по умножению элемент
// предусловие: входной элемент должен быть меньше мощности поля
// постусловие: выходной элемент должен быть меньше мощности поля
qlonglong GF::amul(qlonglong x) const {
#ifdef ERRS
  if ( x >= m_q || x < 0 ) { // проверка предусловия
    error("GF::amul(): входной элемент не принадлежит данному полю.");
  }
#endif

  if (x == 0) return 0;
  if (x == 1) return 1;

  qlonglong i = log(x); // представить элемент x в виде степени примитивного

#ifdef ERRS
  if ( i == -1 ) { // если в таблице не было такого элемента
    error("GF::amul(): в хэш-таблице нет такого элемента.");
  }
#endif

  return alog( m_q-1-i );
}

// вернуть обратный по сложению элемент
// предусловие: входной элемент должен быть меньше мощности поля
// постусловие: выходной элемент должен быть меньше мощности поля
qlonglong GF::aplus(qlonglong x) const {
#ifdef ERRS
  if ( x >= m_q || x < 0 ) { // проверка предусловия
    error("GF::aplus(): входной элемент не принадлежит данному полю.");
  }
#endif

  return x;
}

// возведение в степень элементов конечного поля
// предусловие: входной элемент должен быть меньше мощности поля
// постусловие: выходной элемент должен быть меньше мощности поля
qlonglong GF::power(qlonglong x, qlonglong p) const {
#ifdef ERRS
  if ( x >= m_q || x < 0 ) { // проверка предусловия
    error("GF::power(): входной элемент не принадлежит данному полю.");
  }
#endif

  if ( p == 0 ) return 1;
  if ( p == 1 ) return x;
  if ( x == 0 ) return 0;
  if ( x == 1 ) return 1;

  if ( p < 0 ) {
    p = (-p) % (m_q - 1);
    p = m_q - 1 - p;
  }

  x = log(x);
  x = (x * p) % (m_q - 1);
  x = alog(x);

  return x;
}

// умножение полиномов в конечном поле
// предусловие: входные полиномы не должны быть пустыми
// постусловие: выходной полином не должен быть пуст
QVector<qlonglong> GF::conv(QVector<qlonglong> p1, QVector<qlonglong> p2) const {
#ifdef ERRS
  if ( p1.size() == 0 || p2.size() == 0 ) { // проверка предусловия
    error("GF::conv(): один из входных полиномов пуст.");
  }
#endif

  QVector<qlonglong> res( (p1.size()-1) + (p2.size()-1) + 1, 0 );

  for (int i = 0; i < p1.size(); ++i) {
    for (int j = 0; j < p2.size(); ++j) {
      res[i+j] = plus(  mul( p1.at(i), p2.at(j) ), res.at(i+j)  );
    }
  }

//  res = trunc(res); // убрать нулевые элементы вначале полинома

#ifdef ERRS
  if ( res.size() == 0 ) { // проверка постусловия
    error("GF::conv(): выходной полином пуст.");
  }
#endif

  return res;
}

// сложение полиномов в конечном поле
// предусловие: входные полиномы не должны быть пустыми
// постусловие: выходной полином не должен быть пуст
QVector<qlonglong> GF::add(QVector<qlonglong> p1, QVector<qlonglong> p2) const {
#ifdef ERRS
  if ( p1.size() == 0 || p2.size() == 0 ) { // проверка предусловия
    error("GF::add(): один из входных полиномов пуст.");
  }
#endif

  QVector<qlonglong> res;

  if ( p1.size() > p2.size() ) {
    res = p1;
    for (int i = 0; i < p2.size(); ++i) {
      res[i] = plus( p1.at(i), p2.at(i) );
    }
  }
  else {
    res = p2;
    for (int i = 0; i < p1.size(); ++i) {
      res[i] = plus( p1.at(i), p2.at(i) );
    }
  }

//  res = trunc(res); // убрать нулевые элементы вначале полинома

#ifdef ERRS
  if ( res.size() == 0 ) { // проверка постусловия
    error("GF::add(): выходной полином пуст.");
  }
#endif

  return res;
}

// деление полиномов в конечном поле
// предусловие: входные полиномы не должны быть пустыми
// предусловие: на ноль делить нельзя
// постусловие: выходной полином не должен быть пуст
Deconv GF::deconv(QVector<qlonglong> p1, QVector<qlonglong> p2) const {
#ifdef ERRS
  if ( p1.size() == 0 || p2.size() == 0 ) { // проверка предусловия
    error("GF::deconv(): один из входных полиномов пуст.");
  }
#endif
  Deconv res;

  // !!!!!!!!!!!! может быть стоит добавить возможность использовать полиномы с нулями в
  //              старших степенях

  // ??????????????? КОСТЫЛЬ
  p1 = trunc(p1);
  p2 = trunc(p2);

  if ( p1 == (QVector<qlonglong>() << 0) ) {
    res.div = res.mod = p1;

    return res;
  }

#ifdef ERRS
  if ( p2 == (QVector<qlonglong>() << 0) ) { // проверка предусловия
    error("GF::deconv(): деление на ноль.");
  }
#endif

  if ( p1.size() < p2.size() ) {
    res.div.fill(0, 1);
    res.mod = p1;

    return res;
  }
  else {
    res.div.fill(0, p1.size() - p2.size() + 1);
    res.mod = p1;
  }

  for (qlonglong i = res.mod.size()-1, j = p2.size()-1; i >= j; i = res.mod.size()-1) {
    res.div[i - j] = div( res.mod.last(), p2.last() );
    res.mod        = add( p1, conv(p2, res.div) );
    res.mod        = trunc(res.mod);

    if ( res.mod == (QVector<qlonglong>() << 0) ) {
      break;
    }
  }

  return res;
}

// минимизация длины полинома
// предусловие: входной полином не должен быть пуст
// постусловие: выходной полином не должен быть пуст
QVector<qlonglong> GF::trunc(QVector<qlonglong> p) const {
#ifdef ERRS
  if ( p.size() == 0 ) { // проверка предусловия
    error("GF::trunc(): входной полином пуст.");
  }
#endif

  QVector<qlonglong> res(p);
  // убрать нулевые элементы вначале полинома
  while ( res.size() > 1 && res.last() == 0 ) {
    res.remove( res.size() - 1 );
  }

#ifdef ERRS
  if ( res.size() == 0 ) { // проверка постусловия
    error("GF::trunc(): выходной полином пуст.");
  }
#endif

  return res;
}

// примитивный элемент в степени
// предусловие: степень должна быть меньше мощности поля -2
// постусловие: выходной элемент должен быть меньше мощности поля
qlonglong GF::alog(qlonglong s) const {
#ifdef ERRS
  if ( s > m_q-2 || s < -1 ) { // проверка предусловия
    error("GF::alog(): степень входного элемента не корректна.");
  }
#endif

  if ( s == -1 ) return 0;

  qlonglong res = m_hashTable.value(s, -1);
#ifdef ERRS
  if (res == -1) { // если в таблице нет таких элементов
    error("GF::alog(): в хэш-таблице нет такого элемента.");
  }
#endif

  return res;
}

// степень примитивного элемента
// предусловие: входной элемент должен быть меньше мощности поля
// постусловие: выходной элемент должен быть меньше мощности поля
qlonglong GF::log(qlonglong x) const {
#ifdef ERRS
  if ( x >= m_q || x < 0 ) { // проверка предусловия
    error("GF::log(): входной элемент не принадлежит данному полю.");
  }
#endif

  if ( x == 0 ) return -1;

  qlonglong res = m_hashTable.key(x, -1);
#ifdef ERRS
  if (res == -1) { // если в таблице нет таких элементов
    error("GF::log(): в хэш-таблице нет такого элемента.");
  }
#endif

  return res;
}

// подстановка значения в полином
// предусловие: входной полином должен быть не пуст
qlonglong GF::substitute(QVector<qlonglong> poly, qlonglong x) {
#ifdef ERRS
  if ( poly.size() <= 0 ) { // проверка предусловия
    error("GF::substitute(): входной полином пуст.");
  }
#endif

  qlonglong tmp;
  qlonglong res = 0;

  for (int i = 0; i < poly.size(); ++i) {
    tmp = power( x, i );          // подставить элемент поля вместо 'x^i'
    tmp = mul( poly.at(i), tmp ); // умножить вычисленный 'x^i' на множитель перед ним
    res = plus( res, tmp );       // сложить с остальными частями полинома
  }

  return res;
}

// формальная производная
// предусловие: входной полином должен быть не пуст
QVector<qlonglong> GF::derivative(QVector<qlonglong> poly) {
#ifdef ERRS
  if ( poly.size() <= 0 ) { // проверка предусловия
    error("GF::formalDerivative(): входной полином пуст.");
  }
#endif
  if ( poly.size() == 1 ) return QVector<qlonglong>() << 0;

  QVector<qlonglong> res;

  for (int i = 1; i < poly.size(); ++i) {  // i = 1, т.к. const' = 0
    res.append( i % 2 ? poly.at(i) : 0  ); // в поле с характеристикой 2 четные степени
                                           // отбрасываются
  }

  res = trunc(res); // убрать нули у старших степеней

  return res;
}

// генерация случайного элемента поля
inline qlonglong GF::genElem() const {
  return qrand() % m_q;
}

// генерация случайного полинома заданной длины
// предусловние: входной параметр должен быть положительным
QVector<qlonglong> GF::genPoly(qlonglong len) const {
#ifdef ERRS
  if ( len <= 0 ) { // проверка предусловия
    error("GF::genPoly(): входной параметр не положительный.");
  }
#endif
  QVector<qlonglong> poly(len);

  for (qlonglong i = 0; i < len; ++i) {
    poly[i] = genElem();
  }

  return poly;
}
